Network service providers constantly strive to provide service to their customers during both normal operation and during severe network damage. Some of the customers, such as government and law enforcement agencies, require service during severe network damage when multiple network elements fail because of natural disasters (such as hurricanes or earthquakes), or planned adversary attacks. (The term “network elements” includes, for example, network nodes or links.) Such damage scenarios often divide a service provider network into isolated fragments. Such network fragmentation typically causes the loss of connectivity between critical service equipment connected to different isolated network fragments, making service delivery very difficult.
Network service providers employ modeling to evaluate network survivability during various severe damage scenarios. The total number of failure scenarios to analyze is often astronomically large. For example, in a medium size network with 25 nodes and 100 links the number of possible combinations of single, dual, triple and quadruple link and node failure scenarios is over ten million. The total number of multiple failure scenarios is over 4.25×1037. Hence, it is extremely important to have faster modeling algorithms for evaluating network survivability. The faster the modeling algorithm the more failure scenarios that can be analyzed and the more accurate the resultant survivability analysis.